#include <iostream>
#include <string>
#include <vector>

std::vector<int> compute_next(const std::string &p) {
    int m = p.length();
    std::vector<int> next(m, 0);

    for (int i = 1, j = 0; i < m; ++i) {

        while (j > 0 && p[i] != p[j]) {
            j = next[j - 1];
        }

        if (p[i] == p[j]) {
            j++;
        }

        next[i] = j;
    }

    return next;
}

std::vector<int> kmp_search(const std::string &text, const std::string &p) {
    int n = text.length();
    int m = p.length();

    if (m == 0)
        return {};
    if (n < m)
        return {};

    std::vector<int> next = compute_next(p);
    std::vector<int> res;

    for (int i = 0, j = 0; i < n; ++i) {
        while (j > 0 && text[i] != p[j]) {
            j = next[j - 1];
        }
        if (text[i] == p[j]) {
            j++;
        }
        if (j == m) {
            res.push_back(i - m + 1);
            j = next[j - 1];
        }
    }
    return res;
}

int main() {
    std::string text = "ABABDABACDABABCABAB";
    std::string p = "ABABCABAB";

    std::cout << "Text:    " << text << std::endl;
    std::cout << "p: " << p << std::endl;

    std::vector<int> ans1 = kmp_search(text, p);

    if (ans1.empty()) {
        std::cout << "p not found " << std::endl;
    } else {
        std::cout << "p found at ";
        for (size_t i = 0; i < ans1.size(); ++i) {
            std::cout << ans1[i] << (i == ans1.size() - 1 ? "" : ", ");
        }
        std::cout << std::endl;
    }

    return 0;
}
